# -*- coding: utf-8 -*-

"""剑指 Offer II 039. 直方图最大矩形面积
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：
输入： heights = [2,4]
输出： 4

提示：
1 <= heights.length <=10^5
0 <= heights[i] <= 10^4"""

class Solution:
    """此题可进一步转化为，分别以每个柱子为高，选定其能勾勒的左右最大矩形，再比较每个位置矩形的面积，获得最大面积，
    那么再下降哈，对每个柱子就是求左右两边可以延申的最大宽度；
    那么就有两种方案：其一，对每个柱子，分别向左向右遍历，获取边界；
        其二，对于边界问题，就是上一题获取某天问题之后更高气温的问题，用单调栈撞击的方法，只不过此处是两侧，所以要做两个分别为吃大吃小的单调栈。
        
        
    单独说一下单调栈：
        还是拿计算每个位置最近更高气温问题来说，
        [00,01,02,03,04,05,06,07]
        -------------------------
        [73,74,75,71,69,72,76,73]
        
        想象一个场景，压缩此列表，相邻的元素，如果后面的元素比前面的元素大，就吃掉前面的元素，前面的元素记录是被谁吃的，也就是后面最近能吃到他的；
            不断压缩，最后剩下的都是没有被吃掉的，也就是他们各自后面都没有能吃他们的了，可以发现这些元素从头到尾呈现依次递增或者递减的关系。
        那么怎么实现这个压缩场景呢？可以用单调栈，每次拿到一个新的元素，就用该元素去吃递增/递减栈，直到吃不了为止。
        这种递增/递减的栈，就叫单调栈，比单纯的每个元素，向后挨个遍历比较取值要快"""
    def largestRectangleArea(self, heights) -> int:
        left, right = [0 for _ in heights], [len(heights)-1 for _ in heights]

        stack = []
        for i, height in zip(range(len(heights)), heights):
            while stack and heights[stack[-1]] > height:
                last = stack.pop()
                right[last] = i-1
            stack.append(i)
        
        stack = []
        for i in range(len(heights)-1, -1, -1):
            height = heights[i]
            while stack and heights[stack[-1]] > height:
                last = stack.pop()
                left[last] = i+1
            stack.append(i)

        largest = 0
        for h, l, r in zip(heights,left, right):
            largest = max(h*(r-l+1), largest)
        
        return largest
        

if __name__ == '__main__':
    so = Solution()
    print(so.largestRectangleArea([2,1,5,6,2,3]))
    print(so.largestRectangleArea([2,4]))

